/**
 * @Question.Title: 柱状图中最大的矩形
 * @Question.No: 84
 * @Author: DQ
 * @Date: 2021-04-19 21:04:16
 * @Description: 
 */
//给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 
//
// 求在该柱状图中，能够勾勒出来的矩形的最大面积。 
//
// 
//
// 
//
// 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。 
//
// 
//
// 
//
// 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。 
//
// 
//
// 示例: 
//
// 输入: [2,1,5,6,2,3]
//输出: 10 
// Related Topics 栈 数组 
// 👍 1319 👎 0

package dq.leetcode.editor.cn;

import java.util.Deque;
import java.util.LinkedList;

public class LargestRectangleInHistogram {
    public static void main(String[] args) {
        Solution solution = new LargestRectangleInHistogram().new Solution();
        int[] heights = {3,6,5,7,4,8,1,0};
        System.out.println(solution.largestRectangleArea(heights));
    }
        //leetcode submit region begin(Prohibit modification and deletion)
        class Solution {
            public int largestRectangleArea(int[] heights) {

                int n = heights.length;
                //非严格单调递增栈
                Deque<Integer> stack = new LinkedList<>();

                int ans = 0, s = 0;
                for(int i = 0; i < n; i++){
                    while(!stack.isEmpty() && heights[stack.peek()] > heights[i]){
                        int index = stack.pop();
                        int k = stack.isEmpty()?-1:stack.peek();
                        s = heights[index] * (i-k-1);
                        ans = Math.max(s, ans);
                    }
                    stack.push(i);
                }
                while (!stack.isEmpty()){
                    s = stack.pop();
                    int k = stack.isEmpty() ? n : (n-stack.peek()-1);
                    ans = Math.max(ans, heights[s] * k);
                }
                return ans;
            }
        }
//leetcode submit region end(Prohibit modification and deletion)

}